package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * 很单纯的单链表, 没有用size, 没有双向
 *
 * @author tzp
 * @since 2020/11/18
 */
public class LC707 implements LinkedProblem {
    static class MyLinkedList {
        class Node {
            int value;
            Node next;

            public Node(int value) {
                this.value = value;
            }
        }

        Node head;

        public MyLinkedList() {
        }

        public Node navigateTo(int index) {//0-1, 0/1/2/3
            Node cur = head;
            while (index > 0 && cur != null) {
                cur = cur.next;
                index--;
            }
            return cur;
        }

        public int get(int index) {
            Node cur = navigateTo(index);
            return cur != null ? cur.value : -1;
        }

        public void addAtHead(int val) {
            Node tmp = head;
            head = new Node(val);
            head.next = tmp;
        }

        public void addAtTail(int val) {
            if (head == null) {
                head = new Node(val);
            } else {
                Node cur = head;
                while (cur.next != null) cur = cur.next;
                cur.next = new Node(val);
            }
        }

        public void addAtIndex(int index, int val) {
            if (index == 0) {
                addAtHead(val);
                return;
            }
            Node pre = navigateTo(index - 1);
            if (pre != null) {
                Node tmp = pre.next;
                pre.next = new Node(val);
                pre.next.next = tmp;
            }
        }

        public void deleteAtIndex(int index) {
            if (index == 0) {
                head = head.next;
                return;
            }
            Node pre = navigateTo(index - 1);
            if (pre != null) {
                if (pre.next != null) {
                    pre.next = pre.next.next;
                }
            }
        }
    }

    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtIndex(0, 1);
        linkedList.addAtTail(2);
        linkedList.addAtHead(0);
        linkedList.addAtIndex(1, 100);
        linkedList.deleteAtIndex(1);
        System.out.println(linkedList.get(1));
        System.out.println(linkedList.get(2));
        System.out.println(linkedList.get(3));
        System.out.println(linkedList.get(4));
        System.out.println("xx");
    }
}
